Java面试必备:二分查找算法,你真的会吗?
The following article is from 博文视点Broadview Author 王磊
脚本之家
你与百万开发者在一起
常用的算法有查找算法和排序算法。查找算法有线性查找算法、深度优先搜索算法、广度优先搜索算法和二分查找算法,而最常用也最快速的就是二分查找算法了。
二分查找算法又叫作折半查找,要求待查找的序列有序,每次查找都取中间位置的值与待查关键字进行比较,如果中间位置的值比待查关键字大,则在序列的左半部分继续执行该查找过程,如果中间位置的值比待查关键字小,则在序列的右半部分继续执行该查找过程,直到查找到关键字为止,否则在序列中没有待查关键字。
[3,4,6,20,40,45,51,62,70,99,110] 中查找key=20的数据,根据二分查找算法,只需查找两次便能命中数据。
这里需要强调的是,二分查找算法要求要查找的集合是有序的,如果不是有序的集合,则先要通过排序算法排序后再进行查找。
二分查找算法的Java实现如下,代码定义了方法binarySearch()用于二分查找,在该方法中有3个变量low、mid和high,分别表示二分查找的最小、中间和最大的数据索引。
2 intlow=0;
3 inthigh=array.length-1;
4 intmid;
5 while(low<=high){
6 mid=(low+high)/2;//中间位置
7 if(array[mid]==a){
8 return mid;
9 }else if(a>array[mid]){ //向右查找
10 low=mid+1;
11 }else{ //向左查找
12 high=mid-1;
13 }
14 }
15 return -1;
16 }
在以上代码中,通过一个while循环在数组中查找传入的数据,在该数据大于中间位置的数据时向右查找,即最大索引位置不变,将最小索引设置为上次循环的中间索引加1;在该数据小于中间位置的数据时向左查找,即最小索引位置不变,然后将最大索引设置为上次循环的中间索引并减1。重复以上过程,直到中间索引位置的数据等于要查找的数据,说明找到了要查找的数据,将该数据对应的索引返回。如果遍历到low>high还没有找到要查找的数据,则说明该数据在列表中不存在,返回-1。
面试在即,Java知识点很凌乱?别急,本书是对Java程序员面试必备知识点的总结,详细讲解了JVM原理、多线程、数据结构和算法、分布式缓存、设计模式等内容,除了原理讲解,还有Java实现!希望本书能够帮助你对Java的基础原理有更深入、全面的理解。
王磊,现任国内某知名互联网公司大数据技术架构师,有十余年丰富的物联网及大数据研发和技术架构经验,对物联网及大数据的原理和技术实现有深刻的理解。长期从事海外项目的研发和交付工作,对异地多活数据中心的建设及高可用、高并发系统的设计有丰富的实战经验。
在本文下方留言,发表您在学习Java面试过程中的经验感想,机会总是靠自己去争取来的!小编将对留言进行精选,被精选的留言才会在留言区显示并获得相应的楼层(由于微信留言功能限制,最多只能显示100条)。
踩楼送书活动获奖须知:
1、活动结束时踩中指定楼层的精选留言将获得《Offer来了:Java面试核心知识点精讲(原理篇)》一本,共5名中奖者
2、活动结束我们会在本公众号公布中奖楼层的解压密码,并在3个工作日内收集到获奖用户信息后发出(注意啦:3个工作日未与小编联系视为自动放弃奖品,收到奖品的小伙伴欢迎来留言区晒晒。)
3、获奖楼层下载地址(文件解压密码2019年11月26日公布)
百度云链接:
https://pan.baidu.com/s/1bPvfB0uXGXVtFpasqoh-ZA
提取码: jswv
活动时间
活动时间:即日起至2019年11月26日下午4点整
更多精彩
在公众号后台对话框输入以下关键词
查看更多优质内容!
女朋友 | 大数据 | 运维 | 书单 | 算法
大数据 | JavaScript | Python | 黑客
AI | 人工智能 | 5G | 区块链
机器学习 | 数学 | 留言送书
脚本之家官方书店
觉得不错,请把这篇文章分享给你的朋友
转载 / 投稿请联系:Panda-nian
更多精彩,点击菜单栏“文章”进行查看
●